package main.java.indi.zyj.c150.dps;


import java.util.Scanner;

/**
 *      n个数选取k个和为m
 *      问：
 *          总共有几种方法？
 *
 */
public class _09_SearchNumsSum {

    static int[] a = new int[20];
    static boolean[] selected = new boolean[20];
    static int n, k, sum, ans;


    // 不考虑选取数的问题
    static void Dfs1(int i, int cnt, int s){

        // 剪枝
        if(cnt > k || s > sum){
            return;
        }

        if (i == n){
            if (cnt == k && s == sum){
                ans++;
            }
            return;
        }

        // 不选当前的数字
        Dfs1(i+1, cnt, s);
        // 选当前的数字
        Dfs1(i+1, cnt+1, s+a[i]);


    }

    // 考虑选取数的问题
    static void Dfs2(int cnt, int s){

        // 剪枝
        if(cnt > k || s > sum){
            return;
        }

        if (cnt == n){
            if (s == sum){
                ans++;
            }
        }

        //该循环表示便利数组找满足条件的解 超过条件的直接剪枝
        //从i开始表示选过的不会重复选择  每次循环的下一个项是未搜索过的项
        for (int i = cnt; i < n; i++) {
            if (!selected[i]){
                selected[i] = true;
                Dfs2(cnt+1, s+a[i]);
                selected[i] = false;
            }
        }

    }



    public static void main(String[] args) {


        Scanner scan = new Scanner(System.in);
        System.out.println("请输入数的总数n、选取的个数k以及和m：");
        n = scan.nextInt();
        k = scan.nextInt();
        sum = scan.nextInt();
        System.out.println("请输入目标数组：");
        for (int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
        }

        ans = 0;
//        Dfs1(0, 0, 0);
        Dfs2(0, 0);
        System.out.println(ans);

    }
}
